package 排序;

import java.util.Arrays;

public class Sort {
    /*
        时间复杂度：
        最好：o(n) 执行一次冒泡过程，发现数组有序，排序结束
        平均/最坏：o(n^2)

        空间复杂度：
        o(1)

        稳定性：具备稳定性

    */

public static void bubbleSort(long[] array){
    for (int i = 0; i < array.length - 1; i++){
        // 无序区间：[0, array.length - i) 元素个数：array.length - i
        boolean sorted = true;

        // 内部的循环整体，表示一次冒泡过程
        // 无序区间的相邻的两个元素，需要两两比较一次
        for (int j = 0; j < array.length - i - 1; j++){
            // 永远保证，相邻的两个元素，最大的在后边
            if (array[j] > array[j + 1]){   // 不加等号，具备稳定性

                long t = array[j];
                array[j] = array[j + 1];
                array[j + 1] = t;

                sorted = false;
            }

        }

        if (sorted){
            return;
        }
    }
}

    /*
    * 时复杂度：o(n^2)
    * 空间复杂度:o(1)
    * 稳定性：不具备稳定性
    * */
    public static void selectSort(long[] array){
        for (int i = 0; i < array.length - 1; i++){
            // 无序区间:[0, array.length - i) 元素个数：array.length - i

            // 内部的循环整体，遍历无序区间，找到最大的元素的过程 => 最大元素所在的下标
            int maxElementIndex = -1;
            for (int j = 0; j < array.length - i; j++){
                if (maxElementIndex == -1 || array[j] > array[maxElementIndex]){
                    maxElementIndex = j;
                }
            }

            // 交换，最大的元素 和 无序区间的最后一个元素的位置
            // 要交换，需要最大元素的下标 和 最后一个元素的下标
            Swap.swap(array, maxElementIndex, array.length - 1 - i);
        }
    }


    /*
    * 最好：有序
    * 最坏：逆序
    *
    * 时间复杂度
    * 最好：o(n) 每次插入过程，只需要一个比较
    * 平均/最坏：o(n^2)
    *
    * 空间复杂度：o(1)
    *
    * 稳定性：具备稳定性
    * */
    public static void insertSort(long[] array){
        for (int i = 1; i < array.length; i++){
            // 有序区间：[0, i)
            // 无序区间：[i, array,length)
            long toInsert = array[i];   // 无序区间第一个数
            int j;
            for (j = i - 1; j >= 0 && toInsert < array[j]; j--){    // 不加等号，具备稳定性
                array[j + 1] = array[j];
            }
            array[j + 1] = toInsert;
        }
    }

    /*
    * 时间复杂度：
    * 平均时间复杂度：o(n ^ 1.4 - 1.5)
    *
    * 空间复杂度：
    * o(1)
    *
    * 稳定性：不具备稳定性
    * */
    public static void shellSort(long[] array){
        /* 分组情况
        *  第一次分组： size / 2 组
        *  第二次分组： 上次分组 / 2 组
        *  分组等于 1 相当于最终完成一次插入排序
        * */
        int group = array.length / 2;
        while (true){
            groupInsetSort(array, group);
            if (group == 1){
                // 只有 1 组，并且已经完成玩排序时，停止循环
                return;
            }
            group = group / 2;
        }
    }

    private static void groupInsetSort(long[] array, int group) {
        for (int i = group; i < array.length; i++){
            long toInsert = array[i];
            int j;
            for (j = i - group; j >= 0 && toInsert < array[j]; j -= group){
                array[j + group] = array[j];
            }
            array[j + group] = toInsert;
        }
    }

    /*
    * 不区分情况
    *
    * 时间复杂度：o(n * log(n))
    * 空间复杂度：o(1)
    * 稳定性：不具备稳定性
    * */
public static void heapSort(long[] array){
    creatBigHeap(array);

    for (int i = 0; i < array.length - 1; i++){
        // 无序区间：[0, array.length - i)
        // 交换堆顶元素和无序区间最后一个元素
        long t = array[0];
        array[0] = array[array.length - i - 1];
        array[array.length - i - 1] = t;

        // 无序区间：[0, array.length - i - 1) 元素个数 array.length - i - 1

        shiftDown(array, array.length - i - 1, 0);
    }
}

private static void creatBigHeap(long[] array) {
    for (int i = (array.length - 2) / 2; i >= 0; i--){
        shiftDown(array, array.length, i);
    }
}

private static void shiftDown(long[] array, int length, int index) {
    while (true){
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left >= index){
            return;
        }

        int max = left;
        if (right < index && array[right] > array[left]){
            max = right;
        }

        if (array[index] >= array[max]){
            return;
        }

        long t = array[index];
        array[index] = array[max];
        array[max] = t;

        index = max;
    }
}


}
